﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.Diagnostics.Contracts;

namespace DataStructure.Interview
{
    public class Question53
    {

        public static bool GetBit(int n, int index)
        {
            return ((n & (1 << index) )> 0);
        }

        public static int SetBit(int n, int index, bool b)
        {
            if (b)
            {
                return n | (1 << index);
            }
            else
            {
                return n & ~(1 << index);
            }
        }

        /// <summary>
        /// Number Properties Approach for Next Number
        /// Observations:
        /// » If we “turn on” a 0, we need to “turn off” a 1
        /// » If we turn on a 0 at bit i and turn off a 1 at bit j, the number changes by 2^i - 2^j 
        /// » If we want to get a bigger number with the same number of 1s and 0s, i must be bigger than j 
        /// 1   Traverse from right to left  Once we’ve passed a 1, turn on the next 0  
        /// We’ve now in-creased the number by 2^i   Yikes!  
        /// Example: xxxxx011100 becomes xxxxx111100
        /// 2   Turn off the one that’s just to the right side of that   
        /// We’re now bigger by 2^i - 2^(i-1) 
        /// Example: xxxxx111100 becomes xxxxx101100
        /// 3   Make the number as small as possible by rearranging all the 1s to be as far right as possible: 
        /// Example: xxxxx101100 becomes xxxxx100011
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int GetNext(int n)
        {
            if (n <= 0) return -1;
            int index = 0;
            int countOnes = 0;


            //find first one
            while (!GetBit(n, index)) index++;

            //turn on nex zeor
            while (GetBit(n, index))
            {
                index++;
                countOnes++;
            }

            n = SetBit(n, index, true);


            //ture off previous one 
            index--;
            n = SetBit(n, index, false);
            countOnes--;

            //set zeros
            for (int i = index; i >= countOnes; i--)
            {
                n = SetBit(n, i, false);   
            }

            // set one
            for (int i = countOnes - 1; i >=0; i--)
            {
                n = SetBit(n, i, true);
            }

            return n;

        }
        /// <summary>
        /// To get the previous number, we do the reverse 
        /// 1   Traverse from right to left   Once we’ve passed a zero, 
        /// xxxxx100011 becomes xxxxx000011 
        /// 2   Turn on the 0 that is directly to the right  Example: xxx
        /// xxxxx010011 
        /// 3   Make the number as big as possible by shifting all the
        /// sible  Example: xxxxx010011 becomes xxxxx011100  
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int GetPrevious(int n)
        {
            if (n <= 0) return -1;

            int index = 0;
            int countZeros = 0;
           
            //find first zero
            while (GetBit(n, index)) index++;

            //turn off next 1
            while (!GetBit(n, index))
            {
                index++;
                countZeros++;
            }
            n = SetBit(n, index, false);


            //turn on prevois zero
            index--;
            n = SetBit(n, index, true);
            countZeros--;

            // set ones
            for (int i = index-1; i >= countZeros ; i--)
            {
                n = SetBit(n, i, true);
            }

            // set zero
            for (int i = countZeros -1; i >= 0; i--)
            {
                n = SetBit(n, i, false);
            }

            return 0;
        }

        
    }
}
